The present invention relates to a data error correction apparatus for correcting data errors by using a plurality of error correcting codes.
As a technique for improving the reliability of a data processing system, error correcting codes (ECC) for correcting errors in data have been applied to various kinds of equipment. Especially BCH (Bose-Chaundhuri-Hocqenghen) codes including Reed-Solomon codes are regarded as important because of the high efficiency. Assuming that a primitive polynomial is W(z) and a root of W(z)=0 is xcex1, a Reed-Solomon code is a code on a Galois field having this root a as a primitive element, and it is a kind of a block error correcting code.
FIG. 3 is a block diagram illustrating the structure of an error correction apparatus disclosed in Japanese Published Patent Application No. Hei.5-55926. This error correction apparatus comprises a data memory 72 for storing input data, syndrome calculation circuits 76 and 78 for calculating syndromes of multiple error correcting codes added to the input data, a syndrome memory for storing the syndromes calculated by the syndrome calculation circuits 76 and 78, and an error detection and correction circuit 86 for reading the syndromes stored in the syndrome memory 80 and correcting the error data in the data memory 72. Further, an OR circuit 82 ORs all bits of the calculated syndromes, and the result is stored in a flag memory 84 as flag data indicating data errors. Further, a timing control circuit 88 controls the operation timing of the error correction apparatus. The syndrome calculation circuit 76 comprises adders 20, 22, and 24, delay units 26, 28, and 30, and constant multipliers 32 and 34 for the element of the Galois field, while the syndrome calculation circuit 78 comprises adders 36, 38, and 40, delay units 42, 44, 46, 52, 54, and 56, and constant multipliers 48 and 50. Assuming that input data is Wi and the root of the generating polynomial is am, syndromes S0, S1, and S2 are calculated according to the following formulae (1), (2), and (3).                     S0        =                              ∑                          i              =              1                        n                    ⁢          Wi                                    (        1        )                                S1        =                              ∑                          i              =              1                        n                    ⁢                      Wi            ⁢                          xe2x80x83                        ⁢                          α                              n                -                i                                                                        (        2        )                                S2        =                              ∑                          i              =              1                        n                    ⁢                                    Wi              ⁡                              (                                  α                  2                                )                                                    n              -              i                                                          (        3        )            
Then, the error detection and correction circuit 86 reads the syndromes S0, S1, and S2 from the syndrome memory 80. When at least one of these syndromes is not xe2x80x9c0xe2x80x9d, the position and size of error are calculated according to S0-S2, and the error data in the input data stored in the data memory 72 are corrected according to the result.
In this error correction apparatus, simultaneously with writing the input data applied to the input terminal 70 into the data memory 72, the syndrome calculators 76 and 78 calculate syndromes of the error correcting codes added to the input data, and data errors are corrected on the basis of the syndromes. The corrected data are output from the output terminal 74.
Generally, when performing error correction by using a t-fold (t=integer, txe2x89xa71) error correcting BCH code, 2t syndromes are calculated. For example, in a digital audio tape recorder (DAT), a triple error correcting Reed-Solomon code and a double error correcting Reed-Solomon code are added to correct data errors. In this case, for one code word, six syndromes are calculated for the triple error correcting Reed-Solomon code, and four syndromes are calculated for the double error correcting Reed-Solomon code.
FIG. 2 shows the structure of a conventional syndrome calculation circuit used in a data error correction apparatus. The syndrome calculation circuit comprises six syndrome calculators 300xcx9c305, and these calculators 300xcx9c305 are provided with data input terminals 320xcx9c325, Galois field adders 340xcx9c345, flip-flops 360xcx9c365 as delay units, and constant multipliers 380xcx9c385 for calculating the 0th to 5th powers of an element xcex1 of Galois field (hereinafter referred to as xcex1{circumflex over ( )}0xcx9cxcex1{circumflex over ( )}5 ). In these syndrome calculators 300xcx9c305, every time data of a code word are input to the input terminals 320xcx9c325, starting from the head data, the data held in the flip-flops 360xcx9c365 are subjected to constant multiplication in the constant multipliers 380xcx9c385, and the constant-multiplied data and the input data are added in the adders 340xcx9c345, respectively. Then, the data held by the flip-flops 360xcx9c365 are updated with the data output from the adders 340xcx9c345, whereby syndromes of the error correcting code are calculated. For example, since six syndromes are calculated for the triple error correcting Reed-Solomon code, when calculating the syndromes of the triple error correction Reed-Solomon code by using the syndrome calculators, all of the six syndrome calculators 300xcx9c305 are used. On the other hand, since four syndromes are calculated for the double error correcting Reed-Solomon code, when the syndromes of the double error correcting Reed-Solomon code are calculated by using the syndrome calculators, only four syndrome calculators 300xcx9c303 of relatively low correction abilities are used, and the results from the remaining two syndrome calculators 304 and 305 are not used.
As described above, in the conventional syndrome calculation circuit, syndrome calculations for error correcting codes of different correction abilities, such as the triple error correcting Reed-Solomon code and the double error correcting Reed-Solomon code, are realized by using common hardware. In this case, however, since a difference in error-correcting abilities between the triple error correcting Reed-Solomon code and the double error correcting Reed-Solomon is small, the number of code words to be processed in the syndrome calculation for the triple error correcting Reed-Solomon code should be equal to the number of code words to be processed in the syndrome calculation for the double error correcting Reed-Solomon code. That is, only one code word is processed at one time in both of these syndrome calculations. Especially when the code length is large or the code word has no error, since the error correcting speed of the error correction apparatus is regulated by the syndrome calculation, the efficiency of syndrome calculation should be increased to increase the error correcting speed.
By the way, in a data error correction apparatus for a DVD-ROM, not only data in a DVD-ROM but also data in a CD-ROM or a CD-R should be processed. Since an octuple error correcting Reed-Solomon code and a quintuple error correcting Reed-Solomon code are added to the DVD-ROM while a single error correcting Reed-Solomon code is added to the CD-ROM, syndrome calculations for error correcting codes having greatly different error-correcting abilities are required. In this case, in the syndrome calculation circuit shown in FIG. 2, since sixteen syndromes are calculated for the high error-correcting ability code applied to the DVD-ROM, such as the octuple error correcting Reed-Solomon code, sixteen units of syndrome calculators are required for this calculation. Accordingly, in a data error correction apparatus having such syndrome calculation circuit, by using the sixteen syndrome calculators performing syndrome calculation for a high error-correcting ability code, two syndromes are calculated for a low error-correcting ability code such as the single error correcting Reed-Solomon code. Therefore, when calculating the two syndromes, only two syndrome calculators amongst the sixteen syndrome calculators are used while the remaining fourteen syndrome calculators are not used. Especially when processing plural codes of different error correcting abilities by using a common syndrome calculation circuit, a lot of unused syndrome calculators exist when calculating syndromes of a lower error-correcting ability code, whereby the efficiency of the syndrome calculation is degraded, resulting in difficulty in increasing the data correcting speed.
The present invention is made to solve the above-described problems and has for its object to provide a data error correction apparatus including a syndrome calculation circuit for processing plural codes of different error-correcting abilities, in which syndrome calculation for a code having relatively low error-correcting ability can be performed in parallel to increase the error correcting speed.
Other objects and advantages of the invention will become apparent from the detailed description that follows. The detailed description and specific embodiments described are provided only for illustration since various additions and modifications within the scope of the invention will be apparent to those of skill in the art from the detailed description.
According to an aspect of the present invention, there is provided a data error correction apparatus for correcting errors in data to which an n-fold (n: integer, nxe2x89xa71) error correcting BCH code is added, which n is equal to or larger than 2t (t: integer, txe2x89xa71). The apparatus includes 2n units of syndrome calculators each comprising a first constant multiplier for obtaining an element of Galois field which is used for calculating syndromes of the n-fold (nxe2x89xa72t) error correcting BCH code, an adder for adding data obtained in the first constant multiplier and input data supplied from an input terminal, and a delay unit for updating the retained data with the data output from the adder. In this apparatus, when correcting errors in data to which a t-fold error correcting BCH code is added, in order that the number of code words to be processed in parallel by syndrome calculation for the t-fold error correcting BCH becomes at least twice as large as the number of code words to be processed by syndrome calculation for the n-fold (nxe2x89xa72t) error correcting BCH code, at least 2t units of syndrome calculators among the 2n units of syndrome calculators, other than 2t units of syndrome calculators having relatively low error-correcting abilities, are each provided with a second constant multiplier for obtaining an element of Galois field, which is used for calculating syndromes of the t-fold error correcting BCH code, and a selector for connecting the adder to one of the first constant multiplier and the second constant multiplier. Therefore, the processing speed of syndrome calculation for the t-fold error correcting BCH code having relatively low error-correcting ability is increased by effectively utilizing the syndrome calculators for the n-fold (nxe2x89xa72t) error correcting BCH code having relatively high error-correcting ability, whereby high-speed error correction is realized.